//
// Created by lovep on 2025/3/14.
//
#include <cstdio>
#include <cstdlib>

#include <defination.h>
#include <array.h>


Status SqList_Init(SqList &L) {
    L.elem = (ElemType *) malloc(LIST_INIT_SIZE * sizeof(ElemType));

    // 是否分配成功
    if (!L.elem) {
        exit(OVERFLOW);
    }

    L.length = 0;
    L.listsize = LIST_INIT_SIZE;

    return OK;
}

Status SqList_Print(SqList &L) {
    int head = TRUE;
    for (int i = 0; i < L.length; i++) {
        if (!head) {
            printf("->");
        }
        printf("%d", L.elem[i]);
        head = FALSE;
    }
    return OK;
}

Status SqList_Insert(SqList &L, int i, ElemType x) {
    ElemType *newbase, *p, *q;

    if (i < 1 || i > L.length + 1) {
        return ERROR;
    }

    // 已满分配
    if (L.length >= L.listsize) {
        newbase = (ElemType *) realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
        if (!newbase) {
            exit(OVERFLOW);
        }

        L.elem = newbase;
        L.listsize += LISTINCREMENT;
    }

    q = &(L.elem[i - 1]);
    for (p = &(L.elem[L.length - 1]); p >= q; --p) {
        *(p + 1) = *p;
    }

    *q = x;
    ++L.length;

    return OK;
}

Status SqList_Delete(SqList &L, int i, ElemType &e) {
    ElemType *p, *q;

    if (i < 1 || i > L.length) {
        return ERROR;
    }

    p = &L.elem[i - 1];

    e = *p;

    q = L.elem + L.length - 1;
    for (++p; p <= q; ++p) {
        *(p - 1) = *p;
    }

    --L.length;
    return OK;
}

int SqList_Search(SqList L, ElemType e) {
    int i;
    for (i = 1; i < L.length && L.elem[i - 1] != e; i++);
    if (i <= L.length) return i;

    return 0;
}

Status SqList_Combine(SqList L1, SqList L2, SqList &L) {
    // 将两个顺序表合并为一个新的顺序表
    SqList_Init(L);

    // 定义两个指针
    int i = 0, j = 0;

    // 遍历比较
    while (i < L1.length && j < L2.length) {
        if (L1.elem[i] < L2.elem[j]) {
            SqList_Insert(L, L.length + 1, L1.elem[i]);
            i++;
        } else {
            SqList_Insert(L, L.length + 1, L2.elem[j]);
            j++;
        }
    }

    while (i < L1.length) {
        SqList_Insert(L, L.length + 1, L1.elem[i]);
        i++;
    }

    while (j < L2.length) {
        SqList_Insert(L, L.length + 1, L2.elem[j]);
        j++;
    }


    return OK;
}

Status SqList_Sort(SqList &L) {
    //排序
    for (int i = 0; i < L.length - 1; i++) {
        for (int j = 0; j < L.length - 1 - i; j++) {
            if (L.elem[j] > L.elem[j + 1]) {
                int temp = L.elem[j];
                L.elem[j] = L.elem[j + 1];
                L.elem[j + 1] = temp;
            }
        }
    }

    return OK;
}

Status SqList_Duplicate(SqList &L) {
    // 去重线性表中重复的元素，一定要先排序！！！
    int i = 0, j = 0; // 定义快慢指针

    while (j < L.length) {
        j++;
        if (L.elem[i] != L.elem[j]) {
            i++;
            L.elem[i] = L.elem[j];
        }
    }

    L.length = i;
    return OK;
}
